package leetcode.D600.T525;

import java.util.HashMap;
import java.util.Map;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: 18362
 * @Create: 2022-03-20 16:49:25 星期日
 */

class Solution {
    /**
     * 这一题的思想很巧妙
     * 1、利用cur来记录从nums开始位置到当前位置（i）这一段的情况（0和1谁多，多多少？）
     * 2、遍历到i初，更新cur，判断map中是否存在cur，如果存在，说明[map.get(cur)+1,i]这一段的0和1数量相等，那么更新maxLen
     * 3. 如果map中不存在cur，就将cur->i存入map
     * 时间、空间复杂度均为O(n)，本质上是用一个map来记录前缀和->下标，可以在O(1)知道某一段的0、1个数情况
     */
    public int findMaxLength(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int cur = 0, maxLen = 0;
        for (int i=0; i<nums.length; ++i) {
            cur = nums[i] == 0 ? cur - 1 : cur + 1;
            if (map.containsKey(cur))
                maxLen = Math.max(i - map.get(cur), maxLen);
            else
                map.put(cur, i);
        }
        return maxLen;
    }
}